{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Split a String Into the Max Number of Unique Substrings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #string #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #字符串 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxUniqueSplit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #拆分字符串使唯一子字符串的数目最大"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串 <code>s</code> ，请你拆分该字符串，并返回拆分后唯一子字符串的最大数目。</p>\n",
    "\n",
    "<p>字符串 <code>s</code> 拆分后可以得到若干 <strong>非空子字符串</strong> ，这些子字符串连接后应当能够还原为原字符串。但是拆分出来的每个子字符串都必须是 <strong>唯一的</strong> 。</p>\n",
    "\n",
    "<p>注意：<strong>子字符串</strong> 是字符串中的一个连续字符序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;ababccc&quot;\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>一种最大拆分方法为 [&#39;a&#39;, &#39;b&#39;, &#39;ab&#39;, &#39;c&#39;, &#39;cc&#39;] 。像 [&#39;a&#39;, &#39;b&#39;, &#39;a&#39;, &#39;b&#39;, &#39;c&#39;, &#39;cc&#39;] 这样拆分不满足题目要求，因为其中的 &#39;a&#39; 和 &#39;b&#39; 都出现了不止一次。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;aba&quot;\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>一种最大拆分方法为 [&#39;a&#39;, &#39;ba&#39;] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;aa&quot;\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>无法进一步拆分字符串。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>\n",
    "\t<p><code>1 &lt;= s.length&nbsp;&lt;= 16</code></p>\n",
    "\t</li>\n",
    "\t<li>\n",
    "\t<p><code>s</code> 仅包含小写英文字母</p>\n",
    "\t</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [split-a-string-into-the-max-number-of-unique-substrings](https://leetcode.cn/problems/split-a-string-into-the-max-number-of-unique-substrings/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [split-a-string-into-the-max-number-of-unique-substrings](https://leetcode.cn/problems/split-a-string-into-the-max-number-of-unique-substrings/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"ababccc\"', '\"aba\"', '\"aa\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        visited = set()\n",
    "        maxSplit = 1\n",
    "        def backtrack(index, split):\n",
    "            if index >= n:\n",
    "                nonlocal maxSplit \n",
    "                maxSplit = max(maxSplit, split)\n",
    "            else:\n",
    "                for i in range(index, n):\n",
    "                    substr = s[index: i+1]\n",
    "                    if substr not in visited:\n",
    "                        visited.add(substr)\n",
    "                        backtrack(i + 1, split + 1)\n",
    "                        visited.remove(substr)\n",
    "        backtrack(0, 0)\n",
    "        return maxSplit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def gensep(num):\n",
    "    ret = []\n",
    "    step = 0\n",
    "    while num!=0:\n",
    "        num,ys = divmod(num,2)\n",
    "        if ys==1:\n",
    "            ret.append(step)\n",
    "        step += 1\n",
    "    return ret\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        ret = 1\n",
    "        ln = len(s)\n",
    "        for sep in range(1,1<<(ln-1)):\n",
    "            arr = gensep(sep)\n",
    "            arr.append(len(s))\n",
    "            #print(arr)\n",
    "            if len(arr)>ret:\n",
    "                st = set()\n",
    "                for i in range(len(arr)):\n",
    "                    start = 0\n",
    "                    if i!=0:\n",
    "                        start = arr[i-1]+1\n",
    "                    end = arr[i]+1\n",
    "                    word = s[start:end]\n",
    "                    if word in st:\n",
    "                        break\n",
    "                    st.add(s[start:end])\n",
    "                if len(st)==len(arr):\n",
    "                    ret = len(st)\n",
    "        return ret\n",
    "                \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        res = 1\n",
    "\n",
    "        def traverse(s, idx, track):\n",
    "            nonlocal res\n",
    "            if idx >= n:\n",
    "                res = max(res, len(track))\n",
    "                return\n",
    "            \n",
    "            for i in range(idx, n):\n",
    "                x = s[idx: i+1]\n",
    "                if x not in track:\n",
    "                    track.append(x)\n",
    "                    traverse(s, i+1, track)\n",
    "                    track.pop()\n",
    "\n",
    "        traverse(s, 0, [])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        res = float('-inf')\n",
    "        one = set()\n",
    "        def dfs(i): # i == 0 时是规模最大的原问题，i > 0 时是规模变小的子问题\n",
    "            if i == n:\n",
    "                nonlocal res\n",
    "                res = max(res, len(one))\n",
    "                return\n",
    "            \n",
    "            for j in range(i, n):\n",
    "                t = s[i: j + 1]\n",
    "                if t not in one:\n",
    "                    one.add(t)\n",
    "                    dfs(j + 1)\n",
    "                    one.remove(t)\n",
    "        \n",
    "        dfs(0)\n",
    "        return res\n",
    "\n",
    "# 同 https://leetcode.cn/problems/palindrome-partitioning/description/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        def Backtrack(i):\n",
    "            nonlocal ans\n",
    "            if len(seen) > ans:\n",
    "                ans = len(seen)\n",
    "            if i >= n:\n",
    "                return\n",
    "            for j in range(i + 1, n + 1):\n",
    "                if s[i:j] not in seen:\n",
    "                    seen.add(s[i:j])\n",
    "                    Backtrack(j)\n",
    "                    seen.remove(s[i:j])\n",
    "\n",
    "        ans = 0\n",
    "        n = len(s)\n",
    "        seen = set()\n",
    "        Backtrack(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        res = float('-inf')\n",
    "        one = set()\n",
    "        def dfs(i): # i == 0 时是规模最大的原问题，i > 0 时是规模变小的子问题\n",
    "            if i == n:\n",
    "                nonlocal res\n",
    "                res = max(res, len(one))\n",
    "                return\n",
    "            \n",
    "            for j in range(i, n): # 枚举子串的结束位置\n",
    "                t = s[i: j + 1]\n",
    "                if t not in one:\n",
    "                    one.add(t)\n",
    "                    dfs(j + 1) # 注意是 j + 1 而非 i + 1\n",
    "                    one.remove(t)\n",
    "        \n",
    "        dfs(0)\n",
    "        return res\n",
    "# \n",
    "# 同 https://leetcode.cn/problems/palindrome-partitioning/description/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        # 回溯——我自己写的有点问题！\n",
    "        def dfs(pos,res):\n",
    "            nonlocal ans\n",
    "            if pos >= n:\n",
    "                ans = max(ans,res)\n",
    "            else:\n",
    "                for i in range(pos,n):\n",
    "                    sub = s[pos:i + 1]\n",
    "                    if sub in vis:\n",
    "                        continue\n",
    "                    vis.add(sub)\n",
    "                    dfs(i + 1,res + 1)\n",
    "                    vis.remove(sub)\n",
    "\n",
    "        n = len(s)\n",
    "        vis = set()\n",
    "        ans = 1\n",
    "        dfs(0,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        def backtrack(index: int, split: int):\n",
    "            if index >= length:\n",
    "                nonlocal maxSplit\n",
    "                maxSplit = max(maxSplit, split)\n",
    "            else:\n",
    "                for i in range(index, length):\n",
    "                    substr = s[index:i+1]\n",
    "                    if substr not in seen:\n",
    "                        seen.add(substr)\n",
    "                        backtrack(i + 1, split + 1)\n",
    "                        seen.remove(substr)\n",
    "\n",
    "        length = len(s)\n",
    "        seen = set()\n",
    "        maxSplit = 1\n",
    "        backtrack(0, 0)\n",
    "        return maxSplit\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "\n",
    "        res = -inf \n",
    "        def backtrack(index,path):\n",
    "            # print(index,path)\n",
    "            nonlocal res \n",
    "            if index >= len(s):\n",
    "                res = max(res,len(path))\n",
    "                return \n",
    "            for i in range(index,len(s)):\n",
    "                if s[index:i+1] not in path:\n",
    "                    path.append(s[index:i+1])\n",
    "                    backtrack(i+1,path)\n",
    "                    path.pop()\n",
    "        backtrack(0,[])\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        # f = [[] for _ in range(n)]\n",
    "        # st = set([s[0]])\n",
    "        # f[0].append(st)\n",
    "        # for i in range(1, n):\n",
    "        #     for j in range(i - 1, -1, -1):\n",
    "        #         for st in f[j]:\n",
    "        #             tmp = set(st)\n",
    "        #             tmp.add(s[j+1:i+1])\n",
    "        #             f[i].append(tmp)\n",
    "        # # print(f'{f}')\n",
    "        # return max(len(x) for x in f[-1])\n",
    "\n",
    "\n",
    "\n",
    "        seen = set()\n",
    "\n",
    "        def dfs(i):\n",
    "            nonlocal ans\n",
    "            if n - i + 1 + len(seen) < ans:\n",
    "                return \n",
    "            if i == n:\n",
    "                ans = max(ans, len(seen))\n",
    "                return set()\n",
    "            for j in range(i, n):\n",
    "                cur = s[i:j+1]\n",
    "                if cur not in seen:\n",
    "                    seen.add(cur)\n",
    "                    dfs(j + 1)\n",
    "                    seen.remove(cur)\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        def helper(i: int, path: set[str]):\n",
    "            nonlocal ans\n",
    "            if i >= len(s):\n",
    "                # print(path)\n",
    "                ans = max(ans, len(path))\n",
    "                return\n",
    "            for j in range(i + 1, len(s) + 1):\n",
    "                t = s[i:j]\n",
    "                if t not in path:\n",
    "                    path.add(t)\n",
    "                    helper(j, path)\n",
    "                    path.remove(t)\n",
    "\n",
    "        ans = 0\n",
    "        helper(0, set())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        def f(x):\n",
    "            if x==1:\n",
    "                return True\n",
    "            for l in combinations(range(n-1),x-1):\n",
    "                ss=set()\n",
    "                pre=0\n",
    "                for y in l:\n",
    "                    ss.add(s[pre:y+1])\n",
    "                    pre=y+1\n",
    "                ss.add(s[pre:])\n",
    "                if len(ss)==x:\n",
    "                    return True\n",
    "            return False\n",
    "        for i in range(n,0,-1):\n",
    "            if f(i):\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        # Method 1: 递归\n",
    "        # n = len(s)\n",
    "        # ans = 0\n",
    "\n",
    "        # def dfs(ind, strs):\n",
    "        #     nonlocal n, ans\n",
    "        #     # print(strs)\n",
    "        #     if ind == n:\n",
    "        #         ans = max(ans, len(strs))\n",
    "        #     for i in range(ind+1, n+1):\n",
    "        #         if s[ind: i] not in strs:\n",
    "        #             dfs(i, strs | {s[ind: i]})\n",
    "\n",
    "        # dfs(0, set())\n",
    "        # return ans\n",
    "\n",
    "        # Method 2: 回溯\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        strs = set()\n",
    "\n",
    "        def dfs(ind):\n",
    "            nonlocal n, ans\n",
    "            if ind == n:\n",
    "                ans = max(ans, len(strs))\n",
    "            for i in range(ind+1, n+1):\n",
    "                if s[ind: i] not in strs:\n",
    "                    strs.add(s[ind: i])\n",
    "                    dfs(i)\n",
    "                    strs.remove(s[ind: i])\n",
    "\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        res = float('-inf')\n",
    "        one = set()\n",
    "        def dfs(i): # i == 0时是规模最大的原问题，i > 0 时是规模变小的子问题\n",
    "            if i == n:\n",
    "                nonlocal res\n",
    "                res = max(res, len(one))\n",
    "                return\n",
    "            \n",
    "            for j in range(i, n):\n",
    "                t = s[i: j + 1]\n",
    "                if t not in one:\n",
    "                    one.add(t)\n",
    "                    dfs(j + 1)\n",
    "                    one.remove(t)\n",
    "        \n",
    "        dfs(0)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        self.res = 0\n",
    "        vis = set()\n",
    "        def dfs(idx):\n",
    "            if idx == len(s):\n",
    "                self.res = max(self.res, len(vis))\n",
    "                return\n",
    "            for i in range(idx, len(s)):\n",
    "                if s[idx:i+1] not in vis:\n",
    "                    vis.add(s[idx:i+1])\n",
    "                    dfs(i + 1)\n",
    "                    vis.remove(s[idx:i+1])\n",
    "        dfs(0)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        self.res = 0\n",
    "        vis = set()\n",
    "        def dfs(idx):\n",
    "            if idx == len(s):\n",
    "                self.res = max(self.res, len(vis))\n",
    "                return\n",
    "            for i in range(idx, len(s)):\n",
    "                if len(vis) + len(s) - i <= self.res:\n",
    "                    break\n",
    "                if s[idx:i+1] not in vis:\n",
    "                    vis.add(s[idx:i+1])\n",
    "                    dfs(i + 1)\n",
    "                    vis.remove(s[idx:i+1])\n",
    "        dfs(0)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        res = float('-inf')\n",
    "        one = set()\n",
    "        def dfs(i): # i == 0 时是规模最大的原问题，i > 0 时是规模变小的子问题\n",
    "            if i == n: # i == n 时，子问题规模为0，是边界条件，需要return\n",
    "                nonlocal res\n",
    "                res = max(res, len(one))\n",
    "                return\n",
    "            \n",
    "            for j in range(i, n): # 枚举子串的结束位置\n",
    "                t = s[i: j + 1]\n",
    "                if t not in one:\n",
    "                    one.add(t)\n",
    "                    dfs(j + 1) # 注意是 j + 1 而非 i + 1\n",
    "                    one.remove(t)\n",
    "        \n",
    "        dfs(0)\n",
    "        return res\n",
    "'''\n",
    "1593. 拆分字符串使唯一子串的数目最大\n",
    "    题目含义：拆分给定的字符串，要求拆分后的每个子串唯一，求子串的最大数目，可以通过回溯算法实现。\n",
    "1593同131 https://leetcode.cn/problems/palindrome-partitioning/description/\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        \n",
    "        lst = list(s)\n",
    "        ind = list(range(1, n))\n",
    "        ans = 1\n",
    "        for x in range(1, n):\n",
    "            for item in combinations(ind, x):\n",
    "                tp = lst[:]\n",
    "                for j in item:\n",
    "                    tp[j] = \",\" + tp[j]\n",
    "                cur = (\"\".join(tp)).split(\",\")\n",
    "                if len(cur) == len(set(cur)):\n",
    "                    if len(cur) > ans:\n",
    "                        ans = len(cur)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = float('-inf')\n",
    "        res = []\n",
    "        one = set()\n",
    "        def dfs(i):\n",
    "            if i == n:\n",
    "                nonlocal ans\n",
    "                ans = max(ans, len(one))\n",
    "                return\n",
    "            \n",
    "            for j in range(i, n):\n",
    "                t = s[i: j + 1]\n",
    "                if t not in one:\n",
    "                    one.add(t)\n",
    "                    dfs(j + 1)\n",
    "                    one.remove(t)\n",
    "        \n",
    "        dfs(0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = float('-inf')\n",
    "        res = []\n",
    "        one = set()\n",
    "        def dfs(i):\n",
    "            if i == n:\n",
    "                nonlocal ans\n",
    "                ans = max(ans, len(one))\n",
    "                return\n",
    "            \n",
    "            for j in range(i, n):\n",
    "                t = s[i: j + 1]\n",
    "                if t not in one:\n",
    "                    one.add(t)\n",
    "                    dfs(j + 1)\n",
    "                    one.remove(t)\n",
    "        \n",
    "        dfs(0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        ans = 1\n",
    "        path = set()\n",
    "        n = len(s)\n",
    "        def dfs(i):\n",
    "            nonlocal ans\n",
    "            if i == n:\n",
    "                if len(path) > ans:\n",
    "                    ans = len(path)    \n",
    "                return\n",
    "            # 全加上都不够长\n",
    "            if len(path) + n - i < ans:\n",
    "                return \n",
    "            for j in range(i, n):\n",
    "                t = s[i: j + 1]\n",
    "                if t not in path:\n",
    "                    path.add(t)\n",
    "                    dfs(j + 1)\n",
    "                    path.discard(t)\n",
    "        dfs(0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        # f = [[] for _ in range(n)]\n",
    "        # st = set([s[0]])\n",
    "        # f[0].append(st)\n",
    "        # for i in range(1, n):\n",
    "        #     for j in range(i - 1, -1, -1):\n",
    "        #         for st in f[j]:\n",
    "        #             tmp = set(st)\n",
    "        #             tmp.add(s[j+1:i+1])\n",
    "        #             f[i].append(tmp)\n",
    "        # # print(f'{f}')\n",
    "        # return max(len(x) for x in f[-1])\n",
    "\n",
    "\n",
    "\n",
    "        seen = set()\n",
    "\n",
    "        def dfs(i):\n",
    "            nonlocal ans\n",
    "            if i == n:\n",
    "                ans = max(ans, len(seen))\n",
    "                return set()\n",
    "            for j in range(i, n):\n",
    "                cur = s[i:j+1]\n",
    "                if cur not in seen:\n",
    "                    seen.add(cur)\n",
    "                    dfs(j + 1)\n",
    "                    seen.remove(cur)\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        \n",
    "        self.res = 1\n",
    "        def dfs(size, seen, cur):\n",
    "            if cur == len(s):\n",
    "                self.res = max(self.res, size)\n",
    "                return \n",
    "\n",
    "            for i in range(cur, len(s)):\n",
    "                ss = s[cur:i + 1]\n",
    "                if ss not in seen:\n",
    "                    seen.add(ss)\n",
    "                    dfs(size + 1, seen, i + 1)\n",
    "                    seen.remove(ss)\n",
    "\n",
    "\n",
    "\n",
    "        dfs(0, set(), 0)\n",
    "\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        seen = set()\n",
    "        ans = 0\n",
    "\n",
    "        def traceback(i,cnt):\n",
    "            if i == n:\n",
    "                nonlocal ans\n",
    "                ans = max(ans, cnt)\n",
    "            else:\n",
    "                for j in range(i+1, n+1):\n",
    "                    if cnt + n - j + 1<= ans:\n",
    "                        break\n",
    "                    if (word := s[i:j]) not in seen:\n",
    "                        seen.add(word)\n",
    "                        traceback(j, cnt+1)\n",
    "                        seen.remove(word)\n",
    "        \n",
    "        traceback(0,0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        # n = len(s)\n",
    "        # ans = 0\n",
    "\n",
    "        # def dfs(ind, strs):\n",
    "        #     nonlocal n, ans\n",
    "        #     # print(strs)\n",
    "        #     if ind == n:\n",
    "        #         ans = max(ans, len(strs))\n",
    "        #     for i in range(ind+1, n+1):\n",
    "        #         if s[ind: i] not in strs:\n",
    "        #             dfs(i, strs | {s[ind: i]})\n",
    "\n",
    "        # dfs(0, set())\n",
    "        # return ans\n",
    "\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        strs = set()\n",
    "\n",
    "        def dfs(ind):\n",
    "            nonlocal n, ans\n",
    "            if ind == n:\n",
    "                ans = max(ans, len(strs))\n",
    "            for i in range(ind+1, n+1):\n",
    "                if s[ind: i] not in strs:\n",
    "                    strs.add(s[ind: i])\n",
    "                    dfs(i)\n",
    "                    strs.remove(s[ind: i])\n",
    "\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "\n",
    "        max_count = 0\n",
    "        l = len(s)\n",
    "        used = set()\n",
    "        def inner_maxUniqueSplit(start:int):\n",
    "            nonlocal max_count\n",
    "            if start >= l:\n",
    "                return\n",
    "\n",
    "            if len(used) + l - start < max_count:\n",
    "                return \n",
    "\n",
    "            for i in range(start, len(s)):\n",
    "                s_sub = s[start:i+1]\n",
    "                if s_sub not in used:\n",
    "                    used.add(s_sub)\n",
    "                    if i == l - 1:\n",
    "                        max_count = max(max_count, len(used))\n",
    "                    inner_maxUniqueSplit(i+1)\n",
    "                    used.remove(s_sub)\n",
    "\n",
    "        inner_maxUniqueSplit(0)\n",
    "\n",
    "        return max_count\n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        res = float('-inf')\n",
    "        one = set()\n",
    "        def dfs(i): # i == 0 时是规模最大的原问题，i > 0 时是规模变小的子问题\n",
    "            if i == n:\n",
    "                nonlocal res\n",
    "                res = max(res, len(one))\n",
    "                return\n",
    "            \n",
    "            for j in range(i, n): # 枚举子串的结束位置\n",
    "                t = s[i: j + 1]\n",
    "                if t not in one:\n",
    "                    one.add(t)\n",
    "                    dfs(j + 1) # 注意是 j + 1 而非 i + 1\n",
    "                    one.remove(t)\n",
    "        \n",
    "        dfs(0)\n",
    "        return res\n",
    "'''\n",
    "1593. 拆分字符串使唯一子串的数目最大\n",
    "    题目含义：拆分给定的字符串，要求拆分后的每个子字符串唯一，求子字符串的最大数目，可以通过回溯算法实现。\n",
    "1593同131 https://leetcode.cn/problems/palindrome-partitioning/description/\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        def backtrack(index: int, split: int):\n",
    "            if index >= length:\n",
    "                nonlocal maxSplit\n",
    "                maxSplit = max(maxSplit, split)\n",
    "            else:\n",
    "                for i in range(index, length):\n",
    "                    substr = s[index:i+1]\n",
    "                    if substr not in seen:\n",
    "                        seen.add(substr)\n",
    "                        backtrack(i + 1, split + 1)\n",
    "                        seen.remove(substr)\n",
    "\n",
    "        length = len(s)\n",
    "        seen = set()\n",
    "        maxSplit = 1\n",
    "        backtrack(0, 0)\n",
    "        return maxSplit\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        def fun(star, count, n, M):\n",
    "            if star >= n:\n",
    "                M = max(M, count)\n",
    "            else:\n",
    "                for i in range(star,n):\n",
    "                    sstr = s[star: i + 1]\n",
    "                    if sstr not in S:\n",
    "                        S.add(sstr)\n",
    "                        M = fun(i + 1, count + 1, n, M)\n",
    "                        S.remove(sstr)\n",
    "            return M\n",
    "\n",
    "        n = len(s)\n",
    "        S = set()\n",
    "        M = 1\n",
    "        M = fun(0,0,n,1)\n",
    "        return M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        res = []\n",
    "        n = len(s)\n",
    "\n",
    "        def dfs(path, idx):\n",
    "            if idx == n:\n",
    "                nonlocal max_\n",
    "                if len(path) > max_:\n",
    "                    max_ = len(path)\n",
    "                    print(max_)\n",
    "                return \n",
    "\n",
    "            for i in range(idx, n):\n",
    "                t = s[idx:i+1]\n",
    "                if t not in path:\n",
    "                    dfs(path + [t], i+1)\n",
    "            \n",
    "        max_ = 0\n",
    "        dfs([], 0)\n",
    "\n",
    "        return max_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        maxsplit = 1\n",
    "        length = len(s)\n",
    "        def backtrack(index, split):\n",
    "            nonlocal maxsplit\n",
    "            if index >= length:\n",
    "                maxsplit = max(maxsplit, split)\n",
    "            else:\n",
    "                for i in range(index, length):\n",
    "                    substr = s[index: i+1]\n",
    "                    if substr not in seen:\n",
    "                        seen.add(substr)\n",
    "                        backtrack(i+1, split+1)\n",
    "                        seen.remove(substr)\n",
    "        seen = set()\n",
    "        backtrack(0, 0)\n",
    "        return maxsplit\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = float('-inf')\n",
    "        res = []\n",
    "        one = set()\n",
    "        def dfs(i):\n",
    "            if i == n:\n",
    "                nonlocal ans\n",
    "                ans = max(ans, len(one))\n",
    "                return\n",
    "            \n",
    "            for j in range(i, n):\n",
    "                t = s[i: j + 1]\n",
    "                if t not in one:\n",
    "                    one.add(t)\n",
    "                    dfs(j + 1)\n",
    "                    one.remove(t)\n",
    "        \n",
    "        dfs(0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        def backtrack(index: int, split: int):\n",
    "            if index >= length:\n",
    "                nonlocal maxSplit\n",
    "                maxSplit = max(maxSplit,split)\n",
    "            else:\n",
    "                for i in range(index,length):\n",
    "                    substr = s[index:i+1] #原始字符切片\n",
    "                    if substr not in seen:\n",
    "                        seen.add(substr)\n",
    "                        backtrack(i+1,split+1)\n",
    "                        seen.remove(substr)\n",
    "        length = len(s)\n",
    "        seen = set()\n",
    "        maxSplit = 1\n",
    "        backtrack(0,0)\n",
    "        return maxSplit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        def dfs(s, path, start):\n",
    "            if start == len(s):\n",
    "                nonlocal res\n",
    "                if len(path) > len(res):\n",
    "                    res = copy.deepcopy(path)\n",
    "                return\n",
    "            for i in range(start+1, len(s)+1):\n",
    "                if s[start:i] in path:  continue\n",
    "                path.append(s[start:i])\n",
    "                dfs(s, path, i)\n",
    "                path.pop()\n",
    "        res = []\n",
    "        dfs(s, [], 0)\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        def partition_string(s, k):\n",
    "            if k == 1:\n",
    "                yield [s]  # 当 k 为 1 时，只有一种分法，整个字符串作为一个子字符串\n",
    "            elif k == len(s):\n",
    "                yield [c for c in s]  # 当 k 等于字符串长度时，每个字符作为一个子字符串\n",
    "            else:\n",
    "                for i in range(1, len(s) - k + 2):\n",
    "                    # 将字符串 s 的前 i 个字符作为第一个子字符串\n",
    "                    first_part = s[:i]\n",
    "                    # 递归计算剩余部分的所有分法\n",
    "                    for rest in partition_string(s[i:], k - 1):\n",
    "                        yield [first_part] + rest\n",
    "\n",
    "        def check(s: str, k: int):\n",
    "            res=False\n",
    "            for partition in partition_string(s, k):\n",
    "                if len(set(partition))==len(partition):\n",
    "                    res=True\n",
    "            return res\n",
    "            \n",
    "        for k in range(1, len(s)+1):\n",
    "            if not check(s, k):\n",
    "                return k-1\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        sub_set = set()\n",
    "        n = len(s)\n",
    "        result = 0\n",
    "\n",
    "        def dfs(i):\n",
    "            nonlocal result\n",
    "            if i == n:\n",
    "                result = max(result, len(sub_set))\n",
    "                return\n",
    "            for j in range(i+1, n+1):\n",
    "                if len(sub_set) + n -j + 1 <= result:\n",
    "                    break\n",
    "                if s[i: j] not in sub_set:\n",
    "                    sub_set.add(s[i: j])\n",
    "                    dfs(j)\n",
    "                    sub_set.remove(s[i: j])\n",
    "\n",
    "        dfs(0)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # Backtrack. Time O(2^n) Space O(n)\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        self.res = 0\n",
    "        vis = set()\n",
    "        def dfs(idx):\n",
    "            if idx == len(s):\n",
    "                self.res = max(self.res, len(vis))\n",
    "                return\n",
    "            for i in range(idx, len(s)):\n",
    "                # pruning: if the max number of remaining substrings:\n",
    "                # count(s[idx:i+1], s[i+1], ..., s[len(s)-1]) <= self.res\n",
    "                # stop moving i forward\n",
    "                if len(vis) + len(s) - i <= self.res:\n",
    "                    break\n",
    "                if s[idx:i+1] not in vis:\n",
    "                    vis.add(s[idx:i+1])\n",
    "                    dfs(i + 1)\n",
    "                    vis.remove(s[idx:i+1])\n",
    "        dfs(0)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(ind, strs):\n",
    "            nonlocal n, ans\n",
    "            # print(strs)\n",
    "            if ind == n:\n",
    "                ans = max(ans, len(strs))\n",
    "            for i in range(ind+1, n+1):\n",
    "                if s[ind: i] not in strs:\n",
    "                    dfs(i, strs | {s[ind: i]})\n",
    "\n",
    "        dfs(0, set())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(ind, strs):\n",
    "            nonlocal n, ans\n",
    "            # print(strs)\n",
    "            if ind == n:\n",
    "                ans = max(ans, len(strs))\n",
    "            for i in range(ind+1, n+1):\n",
    "                if s[ind: i] not in strs:\n",
    "                    dfs(i, strs | {s[ind: i]})\n",
    "\n",
    "        dfs(0, set())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # Backtrack. Time O(2^n) Space O(n)\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        self.res = 0\n",
    "        vis = set()\n",
    "        def dfs(idx):\n",
    "            if idx == len(s):\n",
    "                self.res = max(self.res, len(vis))\n",
    "                return\n",
    "            for i in range(idx, len(s)):\n",
    "                # pruning: if the max number of remaining substrings:\n",
    "                # count(s[idx:i+1], s[i+1], ..., s[len(s)-1]) <= self.res\n",
    "                # stop moving i forward\n",
    "                if len(vis) + len(s) - i <= self.res:\n",
    "                    break\n",
    "                if s[idx:i+1] not in vis:\n",
    "                    vis.add(s[idx:i+1])\n",
    "                    dfs(i + 1)\n",
    "                    vis.remove(s[idx:i+1])\n",
    "        dfs(0)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        res = float('-inf')\n",
    "        one = set()\n",
    "        def dfs(i): # i == 0 时是规模最大的原问题，i > 0 时是规模变小的子问题\n",
    "            if i == n:\n",
    "                nonlocal res\n",
    "                res = max(res, len(one))\n",
    "                return\n",
    "            \n",
    "            for j in range(i, n): # 枚举子串的结束位置\n",
    "                t = s[i: j + 1]\n",
    "                if t not in one:\n",
    "                    one.add(t)\n",
    "                    dfs(j + 1) # 注意是 j + 1 而非 i + 1\n",
    "                    one.remove(t)\n",
    "        \n",
    "        dfs(0)\n",
    "        return res\n",
    "# 拆分给定的字符串，要求拆分后的每个子字符串唯一，求子字符串的最大数目，可以通过回溯算法实现。\n",
    "# 同 https://leetcode.cn/problems/palindrome-partitioning/description/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        temp = {}\n",
    "        def dfs(s,temp):\n",
    "            res = 0\n",
    "            for i in range(1,len(s)+1):\n",
    "                flag = s[:i]\n",
    "                if temp.get(flag)==None:\n",
    "                    temp[flag] = 1\n",
    "                    temp_res = dfs(s[i:],temp)+1 \n",
    "                    temp.pop(flag)\n",
    "                    if temp_res>res:\n",
    "                        res = temp_res\n",
    "                else:\n",
    "                    continue\n",
    "            return res\n",
    "        res = dfs(s,temp)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        res = -inf \n",
    "        def backtrack(index,path):\n",
    "            nonlocal res \n",
    "            if index >= len(s):\n",
    "                res = max(res,len(path))\n",
    "                return \n",
    "            for i in range(index,len(s)):\n",
    "                if s[index:i+1] not in path:\n",
    "                    path.append(s[index:i+1])\n",
    "                    backtrack(i+1,path)\n",
    "                    path.pop()\n",
    "        backtrack(0,[])\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "\n",
    "        def dfs(ind, strs):\n",
    "            nonlocal n, ans\n",
    "            print(strs)\n",
    "            if ind == n:\n",
    "                ans = max(ans, len(strs))\n",
    "            for i in range(ind+1, n+1):\n",
    "                if s[ind: i] not in strs:\n",
    "                    dfs(i, strs | {s[ind: i]})\n",
    "\n",
    "        dfs(0, set())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        ans=[]\n",
    "        ans1=1\n",
    "        n=len(s)\n",
    "        st=set()\n",
    "        def f(i):\n",
    "            nonlocal ans1\n",
    "            if i==n:\n",
    "                # ans.append(list(st))\n",
    "                ans1=max(ans1,len(st))\n",
    "                return  \n",
    "            if len(st)+n-i<ans1:\n",
    "                return\n",
    "            for j in range(1,n+1):\n",
    "                k=s[i:i+j]\n",
    "                if k not in st:\n",
    "                    st.add(k)\n",
    "                    f(i+j)\n",
    "                    st.remove(k)\n",
    "            return \n",
    "        \n",
    "        f(0)\n",
    "        # print(ans)\n",
    "        m=1\n",
    "        return ans1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        \n",
    "        def dfs(i, tmp):\n",
    "            nonlocal ans\n",
    "            if i == n:\n",
    "                ans = max(ans, len(tmp))\n",
    "                return set()\n",
    "            for j in range(i, n):\n",
    "                cur = s[i:j+1]\n",
    "                st = set(tmp)\n",
    "                st.add(cur)\n",
    "                dfs(j + 1, st)\n",
    "        dfs(0, set())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def non_negative_hash(s):\n",
    "    return hash(s) & 0xFFFFFFFFFFFFFFFF\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        max_count = [0]  # Using list to hold the mutable state\n",
    "        seen = set()  # Using a set data structure for faster lookup operations\n",
    "        \n",
    "        def dfs(start: int, count: int) -> int:\n",
    "            if start == n:\n",
    "                max_count[0] = max(max_count[0], count)\n",
    "                return count\n",
    "\n",
    "            local_max = 0\n",
    "            for end in range(start + 1, n + 1):\n",
    "                sub = s[start:end]\n",
    "                \n",
    "                if sub in seen:\n",
    "                    continue\n",
    "\n",
    "                seen.add(sub)\n",
    "                local_max = max(local_max, dfs(end, count + 1))\n",
    "                seen.remove(sub)  # Backtrack\n",
    "\n",
    "            max_count[0] = max(max_count[0], local_max)\n",
    "            return local_max\n",
    "\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        sub_set = set()\n",
    "        n = len(s)\n",
    "        result = 0\n",
    "\n",
    "        def dfs(i):\n",
    "            nonlocal result\n",
    "            if i == n:\n",
    "                result = max(result, len(sub_set))\n",
    "                return\n",
    "            for j in range(i+1, n+1):\n",
    "                if s[i: j] not in sub_set:\n",
    "                    sub_set.add(s[i: j])\n",
    "                    dfs(j)\n",
    "                    sub_set.remove(s[i: j])\n",
    "\n",
    "        dfs(0)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "\n",
    "        self.max_count = 0\n",
    "        l = len(s)\n",
    "        used = set()\n",
    "        def inner_maxUniqueSplit(start:int):\n",
    "            if start >= l:\n",
    "                return\n",
    "\n",
    "            if len(used) + l - start < self.max_count:\n",
    "                return \n",
    "\n",
    "            for i in range(start, len(s)):\n",
    "                for j in range(i, len(s)):\n",
    "                    s_sub = s[i:j+1]\n",
    "                    if s_sub not in used:\n",
    "                        used.add(s_sub)\n",
    "                        if j == l - 1:\n",
    "                            self.max_count = max(self.max_count, len(used))\n",
    "                        inner_maxUniqueSplit(j+1)\n",
    "                        used.remove(s_sub)\n",
    "\n",
    "        inner_maxUniqueSplit(0)\n",
    "\n",
    "        return self.max_count\n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        dc=defaultdict(int)\n",
    "        curmax=-1\n",
    "\n",
    "        def dfs(s:str, step:int):\n",
    "            nonlocal curmax\n",
    "            if step+1>curmax and dc[s]==0:\n",
    "                curmax=step+1\n",
    "\n",
    "            for p in range(1,len(s)):\n",
    "                s1=s[0:p]\n",
    "                s2=s[p::]\n",
    "#                print(s,s1,s2,step)\n",
    "                if dc[s1]>0: continue\n",
    "                dc[s1]+=1\n",
    "                dfs(s2,step+1)\n",
    "                dc[s1]-=1\n",
    "\n",
    "        dfs(s,0)\n",
    "        return curmax\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        def backtrack(index: int, split: int):\n",
    "            nonlocal maxSplit\n",
    "            if index >= length:\n",
    "                maxSplit = max(maxSplit, split)\n",
    "            else:\n",
    "                for i in range(index, length):\n",
    "                    substr = s[index:i+1]\n",
    "                    if substr not in seen:\n",
    "                        seen.add(substr)\n",
    "                        backtrack(i + 1, split + 1)\n",
    "                        seen.remove(substr)\n",
    "\n",
    "        length = len(s)\n",
    "        seen = set()\n",
    "        maxSplit = 1\n",
    "        backtrack(0, 0)\n",
    "        return maxSplit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        def dfs(s, path, start):\n",
    "            nonlocal res\n",
    "            if start == len(s):\n",
    "                if len(path) > len(res):\n",
    "                    res = copy.deepcopy(path)\n",
    "                return\n",
    "            for i in range(start+1, len(s)+1):\n",
    "                if s[start:i] in path:  continue\n",
    "                path.append(s[start:i])\n",
    "                dfs(s, path, i)\n",
    "                path.pop()\n",
    "        res = []\n",
    "        dfs(s, [], 0)\n",
    "        return len(res)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        unique = set()\n",
    "        count = 0\n",
    "        def dfs(start):\n",
    "            nonlocal count\n",
    "            if start == len(s):\n",
    "                count = max(count, len(unique))\n",
    "                return\n",
    "            # 剪枝条件：剩余字符数 + 当前已有的唯一子字符串数 <= 当前最大的子字符串数目\n",
    "            if len(s) - start + len(unique) <= count:  \n",
    "                return\n",
    "            for i in range(start, len(s)):\n",
    "                sub_str = s[start: i+1] \n",
    "                if sub_str in unique:\n",
    "                    continue\n",
    "                \n",
    "                unique.add(sub_str)\n",
    "                print(f'  回溯前 =》{unique}')\n",
    "                dfs(i + 1)\n",
    "                unique.remove(sub_str)\n",
    "                print(f'回溯后 =》{unique}')\n",
    "        \n",
    "        dfs(0)\n",
    "        return count\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        self.max_count = 0\n",
    "        self.inner_maxUniqueSplit(s, 0, set())\n",
    "\n",
    "        return self.max_count\n",
    "        \n",
    "    def inner_maxUniqueSplit(self, s: str, start:int, used:set):\n",
    "        if start >= len(s):\n",
    "            return\n",
    "\n",
    "        if len(used) + len(s) - start < self.max_count:\n",
    "            return \n",
    "\n",
    "        for i in range(start, len(s)):\n",
    "            for j in range(i, len(s)):\n",
    "                s_sub = s[i:j+1]\n",
    "                if s_sub not in used:\n",
    "                    used.add(s_sub)\n",
    "                    if j == len(s) - 1:\n",
    "                        self.max_count = max(self.max_count, len(used))\n",
    "                    self.inner_maxUniqueSplit(s, j+1, used)\n",
    "                    used.remove(s_sub)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "\n",
    "        self.max_count = 0\n",
    "        l = len(s)\n",
    "        used = set()\n",
    "        def inner_maxUniqueSplit(start:int):\n",
    "            if start >= l:\n",
    "                return\n",
    "\n",
    "            if len(used) + l - start < self.max_count:\n",
    "                return \n",
    "\n",
    "            for i in range(start, len(s)):\n",
    "                s_sub = s[start:i+1]\n",
    "                if s_sub not in used:\n",
    "                    used.add(s_sub)\n",
    "                    if i == l - 1:\n",
    "                        self.max_count = max(self.max_count, len(used))\n",
    "                    inner_maxUniqueSplit(i+1)\n",
    "                    used.remove(s_sub)\n",
    "\n",
    "        inner_maxUniqueSplit(0)\n",
    "\n",
    "        return self.max_count\n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans = 1\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        words = set()\n",
    "        n = len(s)\n",
    "        def backtracking(startIndex,split):\n",
    "            if startIndex==n:\n",
    "                self.ans = max(self.ans,split)\n",
    "            \n",
    "            for i in range(startIndex,n):\n",
    "                word = s[startIndex:i+1]\n",
    "                if word not in words:\n",
    "                    words.add(word)\n",
    "                    backtracking(i+1,split+1)\n",
    "                    words.remove(word)\n",
    "        \n",
    "        backtracking(0,0)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        def backtrack(index: int, split: int):\n",
    "            if index == length:\n",
    "                nonlocal ans\n",
    "                ans = max(ans, split)\n",
    "            for i in range(index, length):\n",
    "                substr = s[index:i+1]\n",
    "                if substr not in seen:\n",
    "                    seen.add(substr)\n",
    "                    backtrack(i + 1, split + 1)\n",
    "                    seen.remove(substr)\n",
    "\n",
    "        length = len(s)\n",
    "        seen = set()\n",
    "        ans = 1\n",
    "        backtrack(0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        s_len = len(s)\n",
    "        visited = set()\n",
    "        valid = False\n",
    "        res = 0\n",
    "        \n",
    "        def dfs(first):\n",
    "            nonlocal s_len, visited, valid, res\n",
    "            if first == s_len:\n",
    "                res = max(res, len(visited))\n",
    "                return\n",
    "            \n",
    "            for i in range(first, s_len):\n",
    "                if s[first : i+1] in visited:\n",
    "                    continue\n",
    "                visited.add(s[first : i+1])\n",
    "                dfs(i + 1)\n",
    "                visited.remove(s[first : i+1])\n",
    "        \n",
    "        dfs(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        self.s = s\n",
    "        self.d = set()\n",
    "        self.res = 0\n",
    "        self.l = len(s)\n",
    "\n",
    "        def backtrace(index,split):\n",
    "            if index >= self.l:\n",
    "                self.res = max(self.res,split)\n",
    "                return\n",
    "            for i in range(index,self.l):\n",
    "                sub = self.s[index:i+1]\n",
    "                if sub not in self.d:\n",
    "                    self.d.add(sub)\n",
    "                    backtrace(i+1,split+1)\n",
    "                    self.d.remove(sub)\n",
    "        backtrace(0,0)\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        seen = set()\n",
    "        def dfs(i,split):\n",
    "            nonlocal ans\n",
    "            if i == n:\n",
    "                if split > ans:\n",
    "                    ans = split\n",
    "        \n",
    "            for j in range(i,n):\n",
    "                cur = s[i:j+1]\n",
    "                if cur not in seen:\n",
    "                    seen.add(cur)\n",
    "                    dfs(j+1,split+1)\n",
    "                    seen.remove(cur)\n",
    "        dfs(0,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        def backtrack(index: int, split: int):\n",
    "            if index >= length:\n",
    "                nonlocal maxSplit\n",
    "                maxSplit = max(maxSplit, split)\n",
    "            else:\n",
    "                for i in range(index, length):\n",
    "                    substr = s[index:i+1]\n",
    "                    if substr not in seen:\n",
    "                        seen.add(substr)\n",
    "                        backtrack(i + 1, split + 1)\n",
    "                        seen.remove(substr)\n",
    "\n",
    "        length = len(s)\n",
    "        seen = set()\n",
    "        maxSplit = 1\n",
    "        backtrack(0, 0)\n",
    "        return maxSplit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        \n",
    "        self.res = 1\n",
    "        def dfs(path, seen, cur):\n",
    "            if cur == len(s):\n",
    "                self.res = max(self.res, len(path))\n",
    "                return \n",
    "\n",
    "            for i in range(cur, len(s)):\n",
    "                ss = s[cur:i + 1]\n",
    "                if ss not in seen:\n",
    "                    seen.add(ss)\n",
    "                    path.append(ss)\n",
    "                    dfs(path, seen, i + 1)\n",
    "                    path.pop()\n",
    "                    seen.remove(ss)\n",
    "\n",
    "\n",
    "\n",
    "        dfs([], set(), 0)\n",
    "\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "\n",
    "        max_count = 0\n",
    "        l = len(s)\n",
    "        used = set()\n",
    "        def inner_maxUniqueSplit(start:int):\n",
    "            nonlocal max_count\n",
    "            if start >= l:\n",
    "                return\n",
    "\n",
    "            if len(used) + l - start < max_count:\n",
    "                return \n",
    "\n",
    "            for i in range(start, len(s)):\n",
    "                s_sub = s[start:i+1]\n",
    "                if s_sub not in used:\n",
    "                    used.add(s_sub)\n",
    "                    if i == l - 1:\n",
    "                        max_count = max(max_count, len(used))\n",
    "                    inner_maxUniqueSplit(i+1)\n",
    "                    used.remove(s_sub)\n",
    "\n",
    "        inner_maxUniqueSplit(0)\n",
    "\n",
    "        return max_count\n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        # corner case\n",
    "        if len(s) == 1:\n",
    "            return 1\n",
    "\n",
    "        # dfs\n",
    "        def dfs(i, path):\n",
    "            if i == n:\n",
    "                if len(path) > self.res:\n",
    "                    self.res = len(path)\n",
    "                return\n",
    "\n",
    "            for j in range(i, n):\n",
    "                if s[i:j + 1] not in path:\n",
    "                    path.add(s[i:j + 1])\n",
    "                    dfs(j + 1, path)\n",
    "                    path.discard(s[i:j + 1])\n",
    "            return\n",
    "\n",
    "        self.res = float('-inf')\n",
    "        n = len(s)\n",
    "        dfs(0, set())  # 从0开始，到j-1为止\n",
    "\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        maxsplit=1\n",
    "        seen=set()\n",
    "        def backtrack(index,split):\n",
    "            if index>=len(s):\n",
    "                nonlocal maxsplit\n",
    "                maxsplit=max(maxsplit,split)\n",
    "            else:\n",
    "                for i in range(index,len(s)):\n",
    "                    substr=s[index:i+1]\n",
    "                    if substr not in seen:\n",
    "                        seen.add(substr)\n",
    "                        backtrack(i+1, split+1)\n",
    "                        seen.remove(substr)\n",
    "            \n",
    "            \n",
    "        backtrack(0, 0)\n",
    "        return maxsplit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        path = []\n",
    "        ans = 0\n",
    "        def dfs(i: int, j: int):\n",
    "            if i < 0:\n",
    "                ss = set(path) \n",
    "                nonlocal ans \n",
    "                if len(ss) == len(path):\n",
    "                    ans = max(ans, len(ss))\n",
    "                return\n",
    "            #不分\n",
    "            dfs(i - 1, j)\n",
    "            #分\n",
    "            path.append(s[i:j + 1])\n",
    "            dfs(i - 1, i - 1)\n",
    "            path.pop()\n",
    "        n = len(s)\n",
    "        dfs(n - 1, n - 1)\n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxUniqueSplit(self, s: str) -> int:\n",
    "        def dfs(pos, path):\n",
    "            if pos == n:\n",
    "                res.append(len(path))\n",
    "                return\n",
    "            for i in range(pos, n):\n",
    "                if s[pos:i+1] not in path:\n",
    "                    dfs(i+1, path+[s[pos:i+1]])\n",
    "            return\n",
    "        res = []\n",
    "        n = len(s)\n",
    "        dfs(0, [])\n",
    "\n",
    "        return max(res)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
